package leetcode._003;

import java.util.HashSet;

/**
 * @author chengfangming
 * Given a string, find the length of the longest substring without repeating characters.
 *
 * Example 1:
 *
 * Input: "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 * Example 2:
 *
 * Input: "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 * Example 3:
 *
 * Input: "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 *              Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 */

/**
 * 这题暴力解，遍历每个子字符串的子集，看子集的字符集再看子集是否有相同的字符
 * 暴力解
 * @author chengfangming
 */
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (allUnique(s.substring(i, j))){
                    if (j - i >= max) {
                        max = j - i;
                    }
                }
            }
        }
        return max;
    }

    public boolean allUnique(String substring) {
        int n = substring.length();
        HashSet<Character> uniqueSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (uniqueSet.contains(substring.charAt(i))) {
                return false;
            }
            uniqueSet.add(substring.charAt(i));
        }
        return true;
    }
}
